package 双指针

import "sort"

/*
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
同时还满足 nums[i] + nums[j] + nums[k] == 0 。

请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

三数之和
给你一个整数数组 nums, 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i!=j, i!=k 且 j!=k,
同时还满足 nums[i] + nums[j] + nums[k] == 0

请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

0			1 			2		 3 		4 				5
起始位置     左指针										右指针

如果相加>0, 那么右指针向中心移动
如果相加<0, 那么左指针向中心移动

直到左右指针相遇, 结束本层遍历
以此类推, 从1进行这种判断

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
*/
func threeSum(nums []int) [][]int {
	sort.Ints(nums) //先排序
	var res [][]int //声明结果数组

	for i := 0; i < len(nums)-2; i++ { // a = nums[i], b = nums[left], c = nums[right]
		n1 := nums[i] // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
		if n1 > 0 {
			break
		}

		if i > 0 && n1 == nums[i-1] { // 去重a  (如果当前元素和上一个元素相同, 题意规定不能有重复结果集, 需要跳过)
			continue
		}

		l, r := i+1, len(nums)-1 //左指针:i+1位置  右指针:数组末尾
		for l < r {              //只要左右指针不相遇, 持续遍历
			n2, n3 := nums[l], nums[r]
			if n1+n2+n3 == 0 { //如果三个数字相加为0, 加入结果集
				res = append(res, []int{n1, n2, n3})
				for l < r && nums[l] == n2 { // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
					l++
				}
				for l < r && nums[r] == n3 {
					r--
				}
			} else if n1+n2+n3 < 0 {
				l++
			} else {
				r--
			}
		}
	}

	return res
}
